In Lisp language systems, the data is tagged and variables are not compile-time typed. The type of datum can be determined within executable code and datum of any type can be assigned to a variable. Tagging is typically implemented using tagged pointers. Since pointers are so important in Lisp, they are used as economically as possible. For instance, an economy is achieved by combining the address represented by the pointer with bits in the pointer that denote its type. In Lucid's Common Lisp (LCL) and Domain Lisp (DL), this is done by reserving the low 3 bits for tag, aligning all data on 8-byte boundaries, and using displacements on all indirect addresses to "mask" the tag. This method is used by LCL, DL, and Yale's T, and has shown to be a reliable, efficient and extensible technique for pointer-tagging on general purpose machines.
Use of tagging implies a corresponding need for good bit-field manipulators. Although tags can be masked as part of an indirection operation, a tag must be examined to ascertain a type or massage a type, confirming the need for efficient bit-field operations.
The Lisp universe is traditionally thought of as made up of atoms and list cells. Although this view is a correct semantic model, in real Lisp applications, computation on small integers is so common they are considered a special case. Thus, at the lowest level of implementation, there are actually three kinds of objects in the Lisp universe:
CONS-CELLS: the 2 pointer cells from which lists are constructed; PA1 SMALL-INTS: small signed integers, about the size of a pointer bereft of its tag bits; and PA1 OTHER: blocks of storage with extended tags. PA1 000: 30 bit even integer (29 high order bits concatenated with the most significant tag bit (=0) PA1 001: pointer escape (tagged non-arithmetic block or storage) PA1 010: number escape (floating or infinite precision fixed-point) PA1 011: pointer to cons cell PA1 100: 30 bit odd integer (29 high order bits concatenated with the most significant tag bit (=1) PA1 101: symbol escape (property list, value cell, etc.) PA1 110: other immediate escape (i.e., non-integer; e.g.: single character) PA1 111: unused (forwarding-pointer if supported by hardware) PA1 enter function PA1 case on tags of arguments PA1 perform appropriate operation based on result of the case analysis.
A typical assignment of meaning to the three low bit tag values is shown as follows:
Because Lisp is not statistically typed and because functions are defined to operate polymorphically by checking type tags, executing Lisp code repeats the following sequence
(this code is very frequently expanded in-line) PA2 (some or even many tag values may represent type errors)
Though in theory the code for any function must be prepared to cope with arguments of arbitrary type, either by executing different code based on a type dispatch or by detecting and signalling a type error, for almost all functions a unique type accounts for the overwhelming majority of all cases actually encountered. This is most especially true for the fundamental cases of CAR, CDR and the basic arithmetic functions.